package _17_剑指Offer;

import java.util.Arrays;

public class _66_剑指Offer构建乘积数组 {

    public static void main(String[] args) {

        _66_剑指Offer构建乘积数组 v = new _66_剑指Offer构建乘积数组();

        int[] ins = {1, 2, 3, 4, 5};
        System.out.println(Arrays.toString(v.constructArr(ins)));

    }

    public int[] constructArr(int[] a) {
        int aLen = a.length;
        // 构造前向前缀和数组
        int[] prePrefix = new int[aLen + 1];
        // 构造后向前缀和数组
        int[] postPrefix = new int[aLen + 1];
        prePrefix[0] = 1;
        postPrefix[0] = 1;
        for (int i = 1; i <= aLen; i++) {
            prePrefix[i] = prePrefix[i - 1] * a[i - 1];
            postPrefix[i] = postPrefix[i - 1] * a[aLen - i];
        }

        int[] results = new int[aLen];
        for (int i = 1; i <= aLen; i++) {
            results[i - 1] = prePrefix[i - 1] * postPrefix[aLen - i];
        }
        return results;
    }

}
